/*
 * Given Inorder traversal and Preorder traversal, construct Binary Tree
 */
import java.util.List;

class ConstructTree{
	public ConstructTree(){
		
	}
	
	public Node inPreConst(List inorder, List preorder){
		int inPos,prePos;
		List leftIn = null;
		List rightIn = null;
		List leftPre = null;
		List rightPre = null;
		Node node;
		
		// if(inorder.size() == 0 || preorder.size() == 0 || inorder.size() != preoder.size()){
		// 	return null;
		// }
		if(inorder.size != 0 && preorder.size() !=0)	
		{
			int value = preorder.get(0).getValue();
			node = new Node(value);
		
			inPos = inorder.indexOf(preorder.get(0));
			leftIn = inorder.subList(0,inPos-1);
			rightIn = inorder.subList(inPos+1, inorder.size()-1);
		
			prePos = leftIn.size();
			leftPre = preorder.subList(1,prePos);
			rightPre = preorder.subList(prePos+1, preorder.size()-1);
		
			node.setLeft(leftIn,leftPre);
			node.setRight(rightIn, rightPre);
		}
		return node;		
	}
	

	// Node 
	private class Node(){
		int value;
		Node left;
		Node right;
		
		Node(int value, Node left, Node right){
			this.value = value;
			this.left = left;
			this.right = right;
		}
		
		void setValue(int value){
			this.value = value;
		}
		int getValue(){
			return value;
		} 
		void setLeft(Node left){
			this.left = left;
		}
		Node getLeft(){
			return left;
		}
		void setRight(Node right){
			this.right = right;
		}
		Node getRight(){
			return right;
		}
	}
}